Error correcting codes, such as Reed-Solomon codes, have a wide range of applications in digital communications and storage. Reed-Solomon codes, for example, are used to correct errors in many systems including storage devices, wireless communications, and high-speed modem communications. Generally, a Reed-Solomon encoder takes a block of digital data, comprising a sequence of digital information bits, and interprets the data as a sequence of information symbols. Each symbol comprises m bits of the digital information sequence. The block of input data comprises k such information symbols. The Reed-Solomon encoder produces r additional redundant symbols, which are concatenated with the k information symbols to form a codeword comprising n (equal to k plus r) symbols. The parameters of the Reed-Solomon code are indicated by referring to such a code as an RS(n,k) code with m bit symbols.
Errors occur during transmission or storage for a number of reasons, such as noise or interference, or scratches on a storage medium. A Reed-Solomon decoder processes each block and attempts to correct errors and recover the original data. The number and type of errors that can be corrected depends on the characteristics of the Reed-Solomon code. In general, an RS(n,k) decoder can correct any combination of up to r/2 corrupted symbols provided that the remainder of the n symbols of the codeword are correct.
U.S. Pat. No. 5,444,719 to Cox et al., entitled “Adjustable Error-Correction Composite Reed-Solomon Encoder/Syndrome Generator” (hereinafter “Cox”) and incorporated by reference herein, discloses a conventional combined Reed-Solomon encoder/syndrome generator. Cox discloses a Reed-Solomon encoder that cascades r filters with transfer functions of the form
                    H        i            ⁡              (        D        )              =          1              1        +                              α            i                    ⁢          D                      ,where i equals 0, 1, . . . , r−1. Each of the filters Hi(D) can also be used independently to produce the decoder syndrome Si used in a complementary Reed-Solomon decoder. Cox uses the r filters Hi(D) in cascade to perform the Reed-Solomon encoding function, and to perform syndrome computation, the first step of Reed-Solomon decoding. This reduces the amount of hardware required in an implementation utilizing a Reed-Solomon encoder and decoder in the same integrated circuit chip.
Cox's Reed-Solomon encoder implements polynomial filters of degree one. In particular, Cox teaches the use of r subfilters, each of degree one, which are cascaded to produce an encoder transfer function. Cox teaches that these r subfilters can also be used as syndrome calculators. Cox's individual stages of the cascaded filter can be easily disabled, providing for the ability to produce varying amounts of redundancy from the same basic circuit.
The critical path of the Cox Reed-Solomon encoders, however, can be quite long for large values of r. In addition, the Cox Reed-Solomon encoder fails to reduce the number of Galois field multipliers beyond that which is achieved in the case where the generator polynomial is symmetrical. While a conventional encoder that computes r parity symbols has r constant multipliers, if a generator polynomial is symmetrical, the encoder needs only r/2 multipliers. Nonetheless, the Cox Reed-Solomon encoders, still use r multipliers, even when the generator polynomial is symmetrical.
U.S. Pat. No. 6,826,723 to Fredrickson, entitled “Multi-Rate Reed-Solomon Encoders,” (hereinafter “Fredrickson”), assigned to the assignee of the present invention and incorporated by reference herein, discloses a Reed-Solomon encoder that is capable of performing any of a plurality of encoding rates. The disclosed multi-rate Reed-Solomon encoder is comprised of a number of subfilters that is less than the maximum number of symbols of redundancy provided by the Reed-Solomon coding device. Among other benefits, the Fredrickson encoders provide a mechanism for reducing the number of constant multipliers to r/2, provided that the generator polynomial is symmetrical and that the degree of each subfilter is two. (The degree of a subfilter is the degree of its corresponding generator polynomial. A multiple degree subfilter corresponds to a polynomial of degree greater than one.)
While the multi-rate Reed-Solomon encoders disclosed by Fredrickson exhibit a reduced critical path and a reduced number of Galois field multipliers relative to the Cox encoders, the Fredrickson encoders do not generate the syndrome information required for many applications.
A need therefore exists for a composite multi-rate Reed-Solomon encoder/syndrome computer that, like the Fredrikson encoder, comprises a number of subfilters that is less than the number of symbols of redundancy, and therefore enjoys the same consequent benefits, but also, like the Cox encoder/syndrome computer, uses shared hardware for both encoding and syndrome computation.